这道题貌似很多人用的是网络流+分层图。这里介绍一种费用流解法。
可以证明,最后一个人到达的时间是小于第100天的。
那么对于每一趟航班,如果他的起点是,终点为,可搭乘的人的数量为。那我们就对连100条流量为,费用为的边(表示第几天),分别表示第天的航班。
我们跑费用流时,也不是计算最短距离,而是找到起点到终点的一条路径上的一条费用最大的边的最小值。
比如

我们要的路径是,因为
跑一个流量为的费用流即可。
最后,关于,它活了。(貌似只有几十毫秒)。
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define INF 0x3f3f3f3f
const int MAXN = 5005;
int flow , cost;
int n , m , u , v , w , f;
struct node{
int v , w , f , rev;
};
vector< node > Graph[ MAXN + 5 ];
int dis[ MAXN + 5 ] , vis[ MAXN + 5 ];
int prevv[ MAXN + 5 ] , preve[ MAXN + 5 ];
void spfa( int s , int t ) {
queue< int > Que;
memset( dis , 0x3f , sizeof( dis ) );
memset( vis , 0 , sizeof( vis ) );
dis[ s ] = 0 , vis[ s ] = 1 , Que.push( s );
while( !Que.empty( ) ) {
int u = Que.front( );
Que.pop( ) , vis[ u ] = 0;
for( int i = 0 ; i < Graph[ u ].size( ) ; i ++ ) {
int v = Graph[ u ][ i ].v , w = Graph[ u ][ i ].w;
if( w <= dis[ u ] ) continue; //保证一天只坐一班飞机
if( Graph[ u ][ i ].f && dis[ v ] > max( dis[ u ] , w ) ) {
dis[ v ] = max( dis[ u ] , w );
prevv[ v ] = u , preve[ v ] = i;
if( !vis[ v ] )
Que.push( v ) , vis[ v ] = 1;
}
}
}
}
void Costflow( int S , int T ) {
while( 1 ) {
spfa( S , T );
if( !flow || dis[ T ] == INF ) return;
int d = INF;
for( int v = T ; v != S ; v = prevv[ v ] )
d = min( d , Graph[ prevv[ v ] ][ preve[ v ] ].f );
flow -= d , cost = max( cost , dis[ T ] );
for( int v = T ; v != S ; v = prevv[ v ] ) {
Graph[ prevv[ v ] ][ preve[ v ] ].f -=d;
Graph[ v ][ Graph[ prevv[ v ] ][ preve[ v ] ].rev ].f += d;
}
}
}
int main( ) {
scanf("%d %d %d",&n,&m,&flow);
for( int i = 1 ; i <= m ; i ++ ) {
scanf("%d %d %d",&u,&v,&f);
for( int j = 1 ; j <= 105 ; j ++ ) {
w = j;
Graph[ u ].push_back( { v , w , f , Graph[ v ].size( ) } );
Graph[ v ].push_back( { u , -w , 0 , Graph[ u ].size( ) - 1 } );
}
}
Costflow( 1 , n );
printf("%d\n",cost);
return 0;
}